#include <stdio.h>

/*
实例一：
控制台连续输入n个数（可重复），要求从小到大输出（去重后），注意时间不能超过1s。
*/

/*
方法一：桶排序（bucket sort）
该算法的时间复杂度是O(N+M).
*/
void bucketSort(int n) {
    int a[1000], input;
    for (int i = 1; i <= 1000; i++) {
        a[i] = 0;//初始化桶
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input);
        a[input] = 1;//始终标记首次出现的值
    }

    int count;
    for (int i = 1; i <= 1000; i++) {
        //如果当前的桶里有值（其实就是1），那么直接输出当前的下标即可
        if (a[i] == 1) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\n%d", count);
}

/*
方法二：冒泡排序（bubble sort）
该方法的时间复杂度由两个部分组成，一部分是冒泡排序时间复杂度为O(N²)；
另一部分数读入和输出，分别都是O(N)，因此整个算法的时间复杂度是O(2N+N²)，
相对于N²来说，2N可以忽略不计，故最终的时间复杂度为O(N²).
*/
void bubbleSort(int n) {
    int a[1000], tmp, input;
    //依次将控制输入存入数组中
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input);
        a[i] = input;
    }
    //冒泡排序核心
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    //先输出第一个元素
    printf("%d ", a[1]);
    //计数为1
    int count = 1;
    //然后从第二项开始，循环遍历，如果后一项跟前一项不相等，则输出此项，同时计数+1
    for (int i = 2; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            printf("%d ", a[i]);
            count++;
        }
    }
    printf("\n%d", count);
}

/*
方法三：快速排序（quick sort）
快速排序的时间复杂度为O(NlogN)
*/
void quickSort(int left, int right) {
    //这里就写具体代码，具体请参照quickSort.c文件
}


int main() {
    // bucketSort(5);
    // bubbleSort(5);
    return 0;
}